package com.lun.swordtowardoffer2.c14;

public class LongestCommonSubsequence {

	//1. 二维数组
	public int longestCommonSubsequence(String str1, String str2) {
		
		int len1 = str1.length();
		int len2 = str2.length();
		
		int[][] dp = new int[len1 + 1][len2 + 1];
		
		for(int i = 0; i < len1; i++) {
			for(int j = 0; j < len2; j++) {
				if(str1.charAt(i) == str2.charAt(j)) {
					dp[i + 1][j + 1] = dp[i][j] + 1;
				}else {
					dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
				}
			}
		}
		
		
		return dp[len1][len2];
	}
	
	//2. 两行二维数组
	public int longestCommonSubsequence2(String str1, String str2) {
		
		int len1 = str1.length();
		int len2 = str2.length();
		
		if(len1 > len2) {
			return longestCommonSubsequence2(str2, str1);
		}
		
		int[][] dp = new int[2][len2 + 1];
		
		for(int i = 0; i < len1; i++) {
			for(int j = 0; j < len2; j++) {
				if(str1.charAt(i) == str2.charAt(j)) {
					dp[(i + 1) & 1][j + 1] = dp[i & 1][j] + 1;
				}else {
					dp[(i + 1) & 1][j + 1] = Math.max(dp[(i + 1) & 1][j], dp[i & 1][j + 1]);
				}
			}
		}
		
		return dp[len1 & 1][len2];
	}
	
	//3. 一维数组
	/*
	 *      
	 * 
	 * */
	public int longestCommonSubsequence3(String str1, String str2) {
		
		int len1 = str1.length();
		int len2 = str2.length();
		
		if(len1 > len2) {
			return longestCommonSubsequence3(str2, str1);
		}
		
		int[] dp = new int[len2 + 1];
		
		for(int i = 0; i < len1; i++) {
			
			int prev = dp[0];
			
			for(int j = 0; j < len2; j++) {
				int cur;
				if(str1.charAt(i) == str2.charAt(j)) {
					cur = prev + 1;
				}else {
					cur = Math.max(dp[j], dp[j + 1]);
				}
				
				prev = dp[j + 1];
				dp[j + 1] = cur;//画一行图辅助
			}
		}
		
		return dp[len2];
	}
}
